/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/sort-colors
   @Language: C++
   @Datetime: 16-02-09 08:34
   */

class Solution{
public:
	/**
	 * @param nums: A list of integer which is 0, 1 or 2 
	 * @return: nothing
	 */    
	void sortColors(vector<int> &A) {
		// write your code here
		int C[3] = {0,0,0};		// record each color count
		for(int i=A.size(); i; ++C[A[--i]]);
		for(int c=0, i=0; c<3; ++c)
			for(; C[c]--; A[i++]=c);
	} 
};
